#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020/4/24 15:43
# @Author  : yangdy
# @Email   : yangdy@egu360.com
# @File    : 面试题51. 数组中的逆序对.2020-04-24.py
# @Software: PyCharm

__author__ = 'yangdy'

from typing import List


class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        ans = 0

        def work(data):
            ll = len(data)
            l, r = 0, len(data) - 1
            h = (l + r) // 2
            x = data[h]
            data[h] = data[l]
            while l < r:
                while l < r and data[r] > x:
                    r -= 1
                if l < r:
                    data[l] = data[r]
                while l < r and data[l] <= x:
                    l += 1
                if l < r:
                    data[r] = data[l]
            data[l] = x
            ans1 = work(data[:l])
            ans2 = work(data[l + 1:])
            return ans1 + ans2 + (l - 1) * (ll - l - 1)

        ans = work(nums)


solve = Solution()
nn = [7, 5, 6, 4]
print(nn)
print(solve.reversePairs(nn))




